/*
 * Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/license-default.txt to change this license
 * Click nbfs://nbhost/SystemFileSystem/Templates/Classes/Class.java to edit this template
 */
package com.sx.sx1.lintcode.day717;

import java.util.*;

/**
 *
 * @author mac
 */
public class LC1869 {

    static class Solution {

        /**
         * @param matrix: a matrix
         * @return: return how many square submatrices have all ones
         */
        public int countSquares(int[][] matrix) {
            //动态规划
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            int n = matrix.length;
            int m = matrix[0].length;
            int[][] dp = new int[n][m];

            int ans = 0;
            for (int i = 0; i < m; i++) {
                if (matrix[0][i] == 1) {
                    ans++;
                    dp[0][i] = 1;
                }
            }

            for (int i = 0; i < n; i++) {
                if (matrix[i][0] == 1) {
                    ans++;
                    dp[i][0] = 1;
                }
            }

            if (matrix[0][0] == 1) {
                ans--; //如果0位置是1，那么被计算了2次，需要去掉一次
            }

            for (int i = 1; i < n; i++) {
                for (int j = 1; j < m; j++) {
                    //i,j位置依赖左边，上边，和左上角
                    if (matrix[i][j] == 1) {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                        ans += dp[i][j];
                    }
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        int[][] matrix
                = {
                    {0, 1, 1, 1},
                    {1, 1, 1, 1},
                    {0, 1, 1, 1}
                };

        int[][] matrix1
                = {
                    {1, 0, 1},
                    {1, 1, 0},
                    {1, 1, 0}
                };

        Solution obj = new Solution();
        System.out.println(obj.countSquares(matrix));
        System.out.println(obj.countSquares(matrix1));
    }

}


/*
1869 · 统计全为 1 的正方形子矩阵
算法
中等
通过率
71%

题目
题解18
笔记
讨论17
排名
记录
描述
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1 <= arr.length <= 300
1 <= arr[0].length <= 300
样例
示例 1：

输入：
matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：
15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：

输入：
matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：
7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.





样例
示例 1：

输入：
matrix =
{
  {0,1,1,1},
  {1,1,1,1},
  {0,1,1,1}
}
输出：
15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.
示例 2：

输入：
matrix = 
{
  {1,0,1},
  {1,1,0},
  {1,1,0}
}
输出：


 */
